/*
 * @lc app=leetcode.cn id=312 lang=cpp
 *
 * [312] 戳气球
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    // void traversal(vector<int> input){
    //     printf("vector:");
    //     for (int i : input){
    //         printf("%d", i);
    //     }
    //     printf("\n");
    // };
    
    unordered_map<string, int> hashMemory;
    string vec2str(vector<int>& vec){
        stringstream ss;
        // string str;
        copy(vec.begin(),vec.end(),ostream_iterator<int>(ss,""));
        // str=ss.str();
        return ss.str();
    }
    int maxCoins(vector<int>& nums) {
        int size = nums.size();
        if (size==1){return nums[0];}
        else if (size == 2){
            int a = nums[0], b = nums[1];
            return a>b? a*b+a:a*b+b;
        }
        vector<int> results;
        for (int i=0;i<nums.size();i++){
            vector<int> temp = nums;
            temp.erase(temp.begin()+i);
            int last = i==0?1:nums[i-1];
            int next = i==nums.size()-1?1:nums[i+1];
            auto hashIter = hashMemory.find(vec2str(temp));
            if (hashIter!=hashMemory.end()){
                results.emplace_back(hashIter->second+last*nums[i]*next);
            } else {
                results.emplace_back(maxCoins(temp)+last*nums[i]*next);
            }
        }
        int result = *max_element(results.begin(), results.end());
        hashMemory[vec2str(nums)] = result;
        return result;
    }
/*
    // 显然是dp或者更直观地做成递归加存储
    // 但是为了用哈希储存一串数字的结果而去先转成str，再hash显然是愚蠢的
    // 全都是用nums[left, right]啊
    // 实际上这样如果串里有两段一样的也是重复算，但还是比str哈希优雅

    // 小trick是，在两端加上1作为防越界保护数
public:
    vector<vector<int>> rec;
    vector<int> val;

public:
    int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = max(rec[left][right], sum);
        }
        return rec[left][right];
    }

    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        val.resize(n + 2);
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec.resize(n + 2, vector<int>(n + 2, -1));
        return solve(0, n + 1);
    }
*/
};
// @lc code=end
int main(){
    // unordered_map<vector<int>, int> hashMemory;
    auto traverse = [](vector<int> input){
        printf("vector:");
        for (int i : input){
            printf("%d", i);
        }
        printf("\n");
    };
    Solution mySolution;
    printf("construct\n");
    vector<int> test = {8,2,6,8,9,8,1,4,1,5,3,0,7,7,0,4,2,2};
    int result = mySolution.maxCoins(test);
    printf("res %d\n", result);
}
